1. Field of the Invention
The present invention relates to a technology for controlling a multilevel cache memory.
2. Description of the Related Art
A cache memory has been used to temporarily store data and instructions expected to be needed by a processing unit such as a central processing unit (CPU), thereby reducing access latency in a main memory or a bus. That is, a cache memory can alleviate the performance gap between a processing device and a computing device. Among such cache memories is a multilevel cache memory that includes, for example, a level-1 (L1) cache and a level-2 (L2) cache. The L2 cache contains a copy of the contents of the L1 cache. Reference may be had to, for example, International Publication No. WO 2004/046932, and Japanese Patent Application Laid-Open No. H8-6852.
Such a cache is controlled so that a synonym state, that is, a state in which a physical address is registered with a plurality of different virtual addresses, does not arise in the L1 cache. A virtual address (corresponding to an index section of the L1 cache) is registered to an L2 cache tag in the L2 cache. The L2 cache has a cache line that is divided into a plurality of sub-lines each of which contains data. The data is managed by each sub-line.
Structures of the virtual address and the physical address are described below. FIG. 24 is a diagram for explaining the structure of the virtual address and the physical address. VA is a virtual address, and PA is a physical address. VA1 and PA1 are bits higher than indices of the L1 and L2 caches, respectively. VA2 and PA2 are the indices of the L1 and L2 caches, respectively.
VA2 is divided into VA21 (a part that belongs to a virtual page number) and VA22 (a part that belongs to an offset in page). VA3 and PA3 are offsets in cache line of the L1 cache and the L2 cache, respectively. In the L2 cache, PA3 is divided into sub-lines PA31 and PA32. PA31 is a sub-line number, and PA32 is an offset in sub-line.
VA4 and PA4 are a virtual page number and a physical page number, respectively. VA5 and PA5 are offsets in page. When virtual address VA is translated into physical address PA (or physical address PA is translated into virtual address VA), data (bits) stored in VA5 or PA5 is not transformed. In other words, data in VA5 and data in PA5 are identical.
A data structure of the conventional L2 cache is described. FIG. 25 is a diagram of a data structure of the L2 cache according to the conventional technology. PA1 is a registered physical address (corresponding to PA1 shown in FIG. 24). VA21 is a registered virtual index address (corresponding to VA21 shown in FIG. 24). SUB-LINE x ST is a status of a corresponding sub-line, and SUB-LINE x DATA is cache data of a corresponding sub-line, where x is a number. The status contains data that indicates whether the L1 cache or the L2 cache has data for a corresponding sub-line, or data that indicates whether data for the corresponding sub-line is updated.
The L2 cache shown in FIG. 25 employs a method, as one of examples, for managing four sub-lines in an L2 cache line. When a line size of the L1 cache is α, and a line size of the L2 cache is β, a relation between α and β is α×4=β.
Data in the L2 cache is managed by each sub-line. However, because of a resource limitation at an L2 cache-tag section, a common virtual address VA is allocated to four sub-lines. Therefore, when a write back is executed for resolving the synonym state, an entire of the L2 cache line (all of the four sub-lines) becomes a target to be controlled. If each sub-line has its own virtual address VA, it is possible to independently control data by each sub-line (i.e., no interference between sub-lines occurs). However, a resource amount that that has to allocate to the L2 cache-tag section increases in parallel to the number of sub-lines, so that it is impossible to allocate a virtual address VA to each of the sub-lines in the actual state.
A method of controlling cache memory is described according to the conventional technology. FIGS. 26 to 30 are diagrams for explaining the method of controlling the cache memory according to the conventional technology. Three cases are described with reference to FIGS. 26 to 30. In a first case, where data having a physical address PA(a) is register to the L1 cache with a virtual address VA(a), the L1 cache is accessed with the virtual address VA(a). In a second case, where data having a physical address PA(a) is register to the L1 cache with a virtual address VA(a), the L1 cache is accessed with a virtual address VA(b). In a third case, where data having a physical address PA(a) is register to the L1 cache with a virtual address VA(a), the L1 cache is accessed with the virtual address VA(c). A translation lookaside buffer (TLB) shown in FIGS. 26 to 30 stores correspondence data between the virtual address (virtual page number VA4) and the physical address (physical page number PA4).
In the first case, where data having the physical address PA(a) is register to the L1 cache with the virtual address VA(a), the L1 cache is accessed with the virtual address VA(a). As shown in FIG. 26, the L1-cache control unit (not shown) translates an access virtual address (a virtual address to be accessed) VA(a) to a physical page number PA4(a) by referring to the TLB, and searches for the physical page number PA4(a) corresponding to the L1 index of VA2(a). If there is a hit, i.e., L1 cache hit, DATA(a) stored in the L1 cache is returned.
In the second case, where data having the physical address PA(a) is register to the L1 cache with the virtual address VA(a), the L1 cache is accessed with the virtual address VA(b). As a physical page number corresponding to VA(b), the physical page number PA4(a) equal to VA(a) is registered to the TLB, and an offset in page has an identical sub-line number in the L2 cache (for example, sub-line 0). In an example shown in FIG. 27, a registered physical address PA1(a) excluding bits of the L2 index section or lower bits is registered to the L2 cache tag, and data for the L2 line size (i.e., data common to sub-lines) is registered to the L1 cache as an index of VA21(a).
Moreover, a status for each sub-line that indicates whether data having PA1(a) and VA21(a) is in the L2 cache (corresponding to ST0 to ST3) is stored in the L2 cache tag. DATA(a0) to DATA(a3) is in sub-line 0 to sub-line 3 in a single L2 cache line, respectively. Sub-lines 0 to 3 belong to a common line. L2 cache contains DATA(a0) to DATA(a3).
As shown in FIG. 27, the L1-cache control unit translates the access virtual address VA(b) to the physical page number PA(a) by referring to the TLB. Because a physical page number corresponding to the L1 index of VA2(b) is not in the L1 cache, an L1 cache miss occurs. When an L1 cache miss occurs, the L1-cache control unit accesses the L2 cache.
As shown in a bottom half in FIG. 27, data for the physical address PA (a) is registered to the L2 cache as the virtual address VA21(a) that is different from a requested virtual address VA21(b), the L2-cache control unit (not shown) outputs a command for deleting data, that corresponds to all the sub-lines and has the same VA21(a) registered on the L1 index, to the L1-cache control unit to delete the data from the L1 cache. When DATA(ax) is updated to DATA′(ax) in-L1 cache, the L1-cache control unit and the L2-cache control unit write back, in cooperation with each other, updated data to the L2 cache.
After the latest data is written back to the L2 cache, the L2-cache control unit registers data to the L2 cache by using an index of VA21(b), and returns data corresponding to the requested sub-line to the L1 cache (see, a bottom half in FIG. 28).
The L1-cache control unit stores data acquired from the L2-cache control unit in the L1 cache, and outputs the stored data to a requestor (i.e., a not-shown command control unit) as shown in an upper half in FIG. 28.
In the third case, where data having the physical address PA(a) is register to the L1 cache with the virtual address VA(a), the L1 cache is accessed with the virtual address VA(c). As a physical page number corresponding to VA(c), the physical page number PA4(a) equal to VA(a) is registered to the TLB, and a sub-line number of the L2 cache of an offset in page is not identical. In an example shown in FIG. 29, similar to the example shown in FIG. 27, the registered physical address PA1(a) excluding bits of the L2 index section or lower bits is registered to the L2 cache tag, and data for the L2 line size (i.e., data common to sub-lines) is registered to the L1 cache as an index of VA21(a).
As shown in FIG. 29, the L1-cache control unit translates the access virtual address VA(c) to the physical page number PA(a) by referring to TLB. Because a physical page number corresponding to the L1 index of VA2(b) is not in the L1 cache, an L1 cache miss occurs. When an L1 cache miss occurs, the L1-cache control unit accesses the L2 cache.
As shown in a bottom half in FIG. 29, data for the physical address PA(a) is registered to the L2 cache as the virtual address VA21(a) that is different from a requested virtual address VA21(c), the L2-cache control unit outputs a command for deleting data, that corresponds to all the sub-lines and has the same VA21(a) registered on the L1 index, to the L1-cache control unit to delete the data from the L1 cache. When DATA(ax) is updated to DATA′(ax) in L1 cache, the L1-cache control unit and the L2-cache control unit write back, in, cooperation with each other, updated data to the L2 cache.
After the latest data is written back to the L2 cache, the L2-cache control unit registers data to the L2 cache by using an index of VA21(c), and returns data corresponding to the requested sub-line to the L1 cache (see, a bottom half in FIG. 30).
The L1-cache control unit stores data acquired from the L2-cache control unit in the L1 cache, and outputs the stored data to the requestor as shown in an upper half in FIG. 30.
As described above, a cache line of the L2 cache is divided into a plurality of blocks, that is, sub-lines, which makes it possible to manage data by each sub-line.
However, because a common VA21 is used as an L1 index VA21 registered on the L2 cache tag according to the above conventional technology, at a step of re-register of the L1 index VA21 for resolving the synonym state in a process of a requested sub-line, an operation for deleting data registered to the L1 index before re-registered from the L1 cache (write back) is performed for all of the sub-lines in a single L2 cache line.
To solve the above problem, it is conceivable that the L1 index VA21 is set for each sub-line of the L2 cache. However, because data amount stored in the L2 cache tremendously increases in parallel to the number of sub-lines, the idea is unrealistic.
It is significantly important to address an issue for effectively utilizing the limited source of the L2 cache, and eliminating an unnecessary write back of data (i.e., a process of deleting (writing back) data from the L1 cache corresponding to any other sub-line in a line where the requested sub-line)